package org.aplombh.java.awcing.basic.struct.stack;

public class MyMonotoneStack {
    private static final int N = 100010;
    private int[] stack;
    private int tail;

    public MyMonotoneStack() {
        init();
    }

    public void init() {
        if (stack == null) {
            stack = new int[N];
        }
        tail = 0;
    }

    public String push(int x) {
        String result;

        // 输出每个数左边第一个比它小的数
//        while (tail != 0 && stack[tail] >= x) tail--;

        // 将所有栈中比x大的数全部出栈，保证每次入栈后栈保持递增，并且当前数在栈中
        while (tail != 0 && stack[tail] >= x) pop();
        // 输出比当前数左边第一个比它小的数
        if (tail != 0) result = stack[tail] + " ";
        else result = "-1" + " ";
        stack[++tail] = x;
        return result;
    }

    public int pop() {
        return stack[tail--];
    }

    public int query() {
        return stack[tail];
    }

    public String empty() {
        return tail > 0 ? "YES" : "NO";
    }
}
